<?php
/*
剑指 Offer 68 - II. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]





示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。


说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

*/

require_once '../class/TreeNode.class.php';
$nums = [6,2,8,0,4,7,9,null,null,3,5];
$p = 2; $q = 8;
$p = 2; $q = 4;
$root = generateTreeByArray($nums);
$obj = new Code_Offer68();
var_dump($obj->main($root, $p, $q));

class Code_Offer68
{
    public function main($root, $p, $q)
    {
        if (!$root) {
            return null;
        }
        if ($p > $root->val && $q > $root->val) {
            return $this->main($root->right, $p, $q);
        }
        if ($p < $root->val && $q < $root->val) {
            return $this->main($root->left, $p, $q);
        }
        return $root;
    }

}